package LeetCode刷题;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-09-26 20:05
 * @description: Functions of this class is
 * 官方解法：
 * 我们用数组 merged 存储最终的答案。
 *
 * 首先，我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间：
 *
 * 如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾；
 *
 * 否则，它们重合，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。
 *
 * if (intervals.length == 0) {
 *             return new int[0][2];
 *         }
 *         Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);//按区间的第一个元素进行升序排序
 *
 *         List<int[]> merged = new ArrayList<>();//设定一个集合存放
 *         for (int i = 0; i < intervals.length; i++) {
 *             int left = intervals[i][0];//设定当前的左边界
 *             int right = intervals[i][1];//设定当前的有边界
 *             if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < left) {
 *                 //如果当前区间集合为空、或者当前集合中的上一个区间的最右边的界限小于当前的left，说明当前区间是独立的，可以直接加入集合
 *                 merged.add(new int[]{left, right});
 *             } else {//否则的话，说明当前区间与上一个区间的left和right有重合，需要合并区间，合并区间right取两个区间的
 *                 merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], right);
 *                 *******关键就是这一步合并的操作
 *             }
 *         }
 *         return merged.toArray(new int[merged.size()][]);
 **/
public class No合并区间 {
    public static void main(String[] args) {
        int intervals[][] = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
    }

    public static int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);//按所有区间的左边界进行升序排序
        //将第一个区间的左边界和有边界作为初始值
        int ans[][] = new int[intervals.length][2];
        int index = -1;//因为要将第一个区间放入到答案集合中作为参考，所以答案集合的索引要从-1开始，
        for (int[] interval : intervals) {
            if(index==-1||interval[0]>ans[index][1]){
                ans[++index]=interval;
            }
            else{
                ans[index][1]=Math.max(ans[index][1],interval[1]);
            }
        }
        return Arrays.copyOf(ans, index+1);//新的数组可能会有空间多余的情况，这个函数的意思就是保留新数组index那么长的区间
    }
}